{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "source": [
    "# Simple Grover's Search with the Azure Quantum Service\n",
    "\n",
    "This notebook demonstrates how to use Q# and the Azure Quantum service together to search for data with Grover's algorithm, an example of the quantum development technique known as amplitude amplification. By applying a sequence of reflections, this sample prepares a register of qubits in a state marked by a given quantum operation known as an oracle. The oracle used in this sample checks if its input matches a given integer, so that the computational basis state corresponding to that index is prepared with high probability."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "source": [
    "## Grover's diffusion operator\n",
    "First, define the operations that will be used to create the Grover diffusion operator. This can take 30 seconds to run the first time, as the Q# environment is initializing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "jupyter": {
     "outputs_hidden": false,
     "source_hidden": false
    },
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "outputs": [
    {
     "data": {
      "application/x-qsharp-data": "[\"PrepareUniform\",\"PrepareAllOnes\",\"ReflectAboutAllOnes\"]",
      "text/html": [
       "<ul><li>PrepareUniform</li><li>PrepareAllOnes</li><li>ReflectAboutAllOnes</li></ul>"
      ],
      "text/plain": [
       "PrepareUniform, PrepareAllOnes, ReflectAboutAllOnes"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "open Microsoft.Quantum.Arrays;\n",
    "\n",
    "operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl {\n",
    "    ApplyToEachCA(H, inputQubits);\n",
    "}\n",
    "\n",
    "operation PrepareAllOnes(inputQubits : Qubit[]) : Unit is Adj + Ctl {\n",
    "    ApplyToEachCA(X, inputQubits);\n",
    "}\n",
    "\n",
    "operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit {\n",
    "    Controlled Z(Most(inputQubits), Tail(inputQubits));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "source": [
    "Next, define the diffusion operator. This reflects the input qubits about the uniform superposition state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "jupyter": {
     "outputs_hidden": false,
     "source_hidden": false
    },
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "outputs": [
    {
     "data": {
      "application/x-qsharp-data": "[\"ReflectAboutUniform\"]",
      "text/html": [
       "<ul><li>ReflectAboutUniform</li></ul>"
      ],
      "text/plain": [
       "ReflectAboutUniform"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {\n",
    "    within {\n",
    "        // Transform the uniform superposition to all-zero.\n",
    "        Adjoint PrepareUniform(inputQubits);\n",
    "        // Transform the all-zero state to all-ones\n",
    "        PrepareAllOnes(inputQubits);\n",
    "    } apply {\n",
    "        // Now that we've transformed the uniform superposition to the\n",
    "        // all-ones state, reflect about the all-ones state, then let\n",
    "        // the within/apply block transform us back.\n",
    "        ReflectAboutAllOnes(inputQubits);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "source": [
    "## Grover's operation\n",
    "Now we write a Q# operation for Grover's search algorithm. Start by defining an function that will return the number of Grover iterations needed to find a single marked item, given the number of qubits in a register. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "jupyter": {
     "outputs_hidden": false,
     "source_hidden": false
    },
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "outputs": [
    {
     "data": {
      "application/x-qsharp-data": "[\"NIterations\"]",
      "text/html": [
       "<ul><li>NIterations</li></ul>"
      ],
      "text/plain": [
       "NIterations"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "open Microsoft.Quantum.Math;\n",
    "open Microsoft.Quantum.Convert;\n",
    "\n",
    "function NIterations(nQubits : Int) : Int {\n",
    "    let nItems = 1 <<< nQubits; // 2^numQubits\n",
    "    // compute number of iterations:\n",
    "    let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems)));\n",
    "    let nIterations = Round(0.25 * PI() / angle - 0.5);\n",
    "    return nIterations;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "source": [
    "Next, define an operation to reflect the input register about the basis state marked by a given index. This operation defines the input we are trying to find in the main search."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "jupyter": {
     "outputs_hidden": false,
     "source_hidden": false
    },
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "outputs": [
    {
     "data": {
      "application/x-qsharp-data": "[\"ReflectAboutMarked\"]",
      "text/html": [
       "<ul><li>ReflectAboutMarked</li></ul>"
      ],
      "text/plain": [
       "ReflectAboutMarked"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "operation ReflectAboutMarked(idxMarked : Int, inputQubits : Qubit[]) : Unit {\n",
    "    use outputQubit = Qubit();\n",
    "    within {\n",
    "        // We initialize the outputQubit to (|0⟩ - |1⟩) / √2,\n",
    "        // so that toggling it results in a (-1) phase.\n",
    "        X(outputQubit);\n",
    "        H(outputQubit);\n",
    "    } apply {\n",
    "        // Flip the outputQubit for marked states.\n",
    "        // Here, we get the state given by the index idxMarked.\n",
    "        (ControlledOnInt(idxMarked, X))(inputQubits, outputQubit);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "source": [
    "Finally, we apply Grover's algorithm to search all possible inputs to an operation to find a particular marked state. To do this, we create an operation that takes the number of qubits to be allocated and the index of the marked item to be found. The output will be the computational basis state found in the final measurement. The output should be a little-endian representation of the marked index."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "jupyter": {
     "outputs_hidden": false,
     "source_hidden": false
    },
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "outputs": [
    {
     "data": {
      "application/x-qsharp-data": "[\"SearchForMarkedInput\"]",
      "text/html": [
       "<ul><li>SearchForMarkedInput</li></ul>"
      ],
      "text/plain": [
       "SearchForMarkedInput"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation SearchForMarkedInput(nQubits : Int, idxMarked : Int) : Result[] {\n",
    "    use qubits = Qubit[nQubits];\n",
    "    // Initialize a uniform superposition over all possible inputs.\n",
    "    PrepareUniform(qubits);\n",
    "    // The search itself consists of repeatedly reflecting about the\n",
    "    // marked state and our start state, which we can write out in Q#\n",
    "    // as a for loop.\n",
    "    for _ in 0..NIterations(nQubits) - 1 {\n",
    "        ReflectAboutMarked(idxMarked, qubits);\n",
    "        ReflectAboutUniform(qubits);\n",
    "    }\n",
    "    // Measure and return the answer.\n",
    "    return ForEach(MResetZ, qubits);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "source": [
    "We can run a local simulation of this operation using the [`%simulate`](https://docs.microsoft.com/qsharp/api/iqsharp-magic/simulate) command."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "jupyter": {
     "outputs_hidden": false,
     "source_hidden": false
    },
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "outputs": [
    {
     "data": {
      "application/x-qsharp-data": "[0,1,1]",
      "text/html": [
       "<ul><li>Zero</li><li>One</li><li>One</li></ul>"
      ],
      "text/plain": [
       "Zero, One, One"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%simulate SearchForMarkedInput nQubits=3 idxMarked=6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "source": [
    "## Running Grover's algorithm in Azure Quantum\n",
    "To run the operation on the Azure Quantum service, you must first connect to your workspace by running [`%azure.connect`](https://docs.microsoft.com/qsharp/api/iqsharp-magic/azure.connect) with the workspace's resource ID and location."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "jupyter": {
     "outputs_hidden": false,
     "source_hidden": false
    },
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "outputs": [],
   "source": [
    "%azure.connect \"\" location=\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "source": [
    "Then use [`%azure.target`](https://docs.microsoft.com/qsharp/api/iqsharp-magic/azure.target) to select the target you'd like to use for job submission. This may take a minute or so. Note that this specific sample is not supported for Rigetti targets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "jupyter": {
     "outputs_hidden": false,
     "source_hidden": false
    },
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Loading package Microsoft.Quantum.Providers.IonQ and dependencies...\n",
      "Active target is now ionq.simulator\n"
     ]
    },
    {
     "data": {
      "application/x-qsharp-data": "{\"id\":\"ionq.simulator\",\"current_availability\":{},\"average_queue_time\":1}",
      "text/html": [
       "<table><thead><tr><th style=\"text-align: start;\">Target ID</th><th style=\"text-align: start;\">Current Availability</th><th style=\"text-align: start;\">Average Queue Time (Seconds)</th></tr></thead><tbody><tr><td style=\"text-align: start;\">ionq.simulator</td><td style=\"text-align: start;\">Available</td><td style=\"text-align: start;\">1</td></tr></tbody></table>"
      ],
      "text/plain": [
       "Target ID      Current Availability Average Queue Time (Seconds)\n",
       "-------------- --------- -\n",
       "ionq.simulator Available 1\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%azure.target ionq.simulator"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "source": [
    "To submit the job, use [`%azure.submit`](https://docs.microsoft.com/qsharp/api/iqsharp-magic/azure.submit) with the Q# operation name and any required parameters. This will return immediately after the job is created. Alternatively, you can use [`%azure.execute`](https://docs.microsoft.com/qsharp/api/iqsharp-magic/azure.execute)., which will submit the job and wait for it to complete. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "jupyter": {
     "outputs_hidden": false,
     "source_hidden": false
    },
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "outputs": [],
   "source": [
    "%azure.submit SearchForMarkedInput nQubits=3 idxMarked=6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "source": [
    "You can check the status of the job using [`%azure.status`](https://docs.microsoft.com/qsharp/api/iqsharp-magic/azure.status). Calling this command without any input will check the status of the job most recently submitted in this session. You can also pass a job ID to check the status of a different job."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "jupyter": {
     "outputs_hidden": false,
     "source_hidden": false
    },
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "outputs": [],
   "source": [
    "%azure.status"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "source": [
    "Once the job is complete, you can view the output using the [`%azure.output`](https://docs.microsoft.com/qsharp/api/iqsharp-magic/azure.output) command. This magic command will also accept a job ID to check the output of a previously submitted job."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "jupyter": {
     "outputs_hidden": false,
     "source_hidden": false
    },
    "nteract": {
     "transient": {
      "deleting": false
     }
    }
   },
   "outputs": [
    {
     "data": {
      "application/x-qsharp-data": "{\"[0,0,0]\":0.0078125,\"[1,0,0]\":0.0078125,\"[0,1,0]\":0.0078125,\"[1,1,0]\":0.0078125,\"[0,0,1]\":0.0078125,\"[1,0,1]\":0.0078125,\"[0,1,1]\":0.9453125,\"[1,1,1]\":0.0078125}",
      "text/html": [
       "\r\n",
       "                    <table style=\"table-layout: fixed; width: 100%\">\r\n",
       "                        <thead>\r\n",
       "                            <tr>\r\n",
       "                                <th style=\"text-align: left; width: 25ch\">Result</th>\r\n",
       "                                <th style=\"text-align: left; width: 25ch\">Frequency</th>\r\n",
       "                                <th style=\"text-align: left; width: calc(100% - 25ch - 25ch)\">Histogram</th>\r\n",
       "                            </tr>\r\n",
       "                        </thead>\r\n",
       "                        <tbody>\r\n",
       "                            \r\n",
       "                            <tr>\r\n",
       "                                <td style=\"text-align: left; width: 25ch\">[0,0,0]</td>\r\n",
       "                                <td style=\"text-align: left; width: 25ch\">0.0078125</td>\r\n",
       "                                <td style=\"text-align: left; width: calc(100% - 25ch - 25ch)\">\r\n",
       "                                    <progress\r\n",
       "                                        max=\"100\"\r\n",
       "                                        value=\"0.78125\"\r\n",
       "                                        style=\"width: 100%;\"\r\n",
       "                                    >\r\n",
       "                                </td>\r\n",
       "                            </tr>\r\n",
       "                        \n",
       "\r\n",
       "                            <tr>\r\n",
       "                                <td style=\"text-align: left; width: 25ch\">[1,0,0]</td>\r\n",
       "                                <td style=\"text-align: left; width: 25ch\">0.0078125</td>\r\n",
       "                                <td style=\"text-align: left; width: calc(100% - 25ch - 25ch)\">\r\n",
       "                                    <progress\r\n",
       "                                        max=\"100\"\r\n",
       "                                        value=\"0.78125\"\r\n",
       "                                        style=\"width: 100%;\"\r\n",
       "                                    >\r\n",
       "                                </td>\r\n",
       "                            </tr>\r\n",
       "                        \n",
       "\r\n",
       "                            <tr>\r\n",
       "                                <td style=\"text-align: left; width: 25ch\">[0,1,0]</td>\r\n",
       "                                <td style=\"text-align: left; width: 25ch\">0.0078125</td>\r\n",
       "                                <td style=\"text-align: left; width: calc(100% - 25ch - 25ch)\">\r\n",
       "                                    <progress\r\n",
       "                                        max=\"100\"\r\n",
       "                                        value=\"0.78125\"\r\n",
       "                                        style=\"width: 100%;\"\r\n",
       "                                    >\r\n",
       "                                </td>\r\n",
       "                            </tr>\r\n",
       "                        \n",
       "\r\n",
       "                            <tr>\r\n",
       "                                <td style=\"text-align: left; width: 25ch\">[1,1,0]</td>\r\n",
       "                                <td style=\"text-align: left; width: 25ch\">0.0078125</td>\r\n",
       "                                <td style=\"text-align: left; width: calc(100% - 25ch - 25ch)\">\r\n",
       "                                    <progress\r\n",
       "                                        max=\"100\"\r\n",
       "                                        value=\"0.78125\"\r\n",
       "                                        style=\"width: 100%;\"\r\n",
       "                                    >\r\n",
       "                                </td>\r\n",
       "                            </tr>\r\n",
       "                        \n",
       "\r\n",
       "                            <tr>\r\n",
       "                                <td style=\"text-align: left; width: 25ch\">[0,0,1]</td>\r\n",
       "                                <td style=\"text-align: left; width: 25ch\">0.0078125</td>\r\n",
       "                                <td style=\"text-align: left; width: calc(100% - 25ch - 25ch)\">\r\n",
       "                                    <progress\r\n",
       "                                        max=\"100\"\r\n",
       "                                        value=\"0.78125\"\r\n",
       "                                        style=\"width: 100%;\"\r\n",
       "                                    >\r\n",
       "                                </td>\r\n",
       "                            </tr>\r\n",
       "                        \n",
       "\r\n",
       "                            <tr>\r\n",
       "                                <td style=\"text-align: left; width: 25ch\">[1,0,1]</td>\r\n",
       "                                <td style=\"text-align: left; width: 25ch\">0.0078125</td>\r\n",
       "                                <td style=\"text-align: left; width: calc(100% - 25ch - 25ch)\">\r\n",
       "                                    <progress\r\n",
       "                                        max=\"100\"\r\n",
       "                                        value=\"0.78125\"\r\n",
       "                                        style=\"width: 100%;\"\r\n",
       "                                    >\r\n",
       "                                </td>\r\n",
       "                            </tr>\r\n",
       "                        \n",
       "\r\n",
       "                            <tr>\r\n",
       "                                <td style=\"text-align: left; width: 25ch\">[0,1,1]</td>\r\n",
       "                                <td style=\"text-align: left; width: 25ch\">0.9453125</td>\r\n",
       "                                <td style=\"text-align: left; width: calc(100% - 25ch - 25ch)\">\r\n",
       "                                    <progress\r\n",
       "                                        max=\"100\"\r\n",
       "                                        value=\"94.53125\"\r\n",
       "                                        style=\"width: 100%;\"\r\n",
       "                                    >\r\n",
       "                                </td>\r\n",
       "                            </tr>\r\n",
       "                        \n",
       "\r\n",
       "                            <tr>\r\n",
       "                                <td style=\"text-align: left; width: 25ch\">[1,1,1]</td>\r\n",
       "                                <td style=\"text-align: left; width: 25ch\">0.0078125</td>\r\n",
       "                                <td style=\"text-align: left; width: calc(100% - 25ch - 25ch)\">\r\n",
       "                                    <progress\r\n",
       "                                        max=\"100\"\r\n",
       "                                        value=\"0.78125\"\r\n",
       "                                        style=\"width: 100%;\"\r\n",
       "                                    >\r\n",
       "                                </td>\r\n",
       "                            </tr>\r\n",
       "                        \r\n",
       "                        </tbody>\r\n",
       "                    </table>\r\n",
       "                "
      ],
      "text/plain": [
       "Result  Frequency\n",
       "------- ---------\n",
       "[0,0,0] 0.0078125\n",
       "[1,0,0] 0.0078125\n",
       "[0,1,0] 0.0078125\n",
       "[1,1,0] 0.0078125\n",
       "[0,0,1] 0.0078125\n",
       "[1,0,1] 0.0078125\n",
       "[0,1,1] 0.9453125\n",
       "[1,1,1] 0.0078125\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%azure.output"
   ]
  }
 ],
 "metadata": {
  "kernel_info": {
   "name": "iqsharp"
  },
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.14"
  },
  "nteract": {
   "version": "nteract-front-end@1.0.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
